package C059;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c05
 * Package: C059
 * Description:  盖章问题
 * https://leetcode.cn/problems/stamping-the-sequence/description/
 * 还是很难的，很值得回味的一道题目
 * @Author BCXJ
 * @Create 2025/11/9 17:13
 * @Version 1.0
 * @Since 1.0
 */
public class c05 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(movesToStamp("abc", "abcbc")));
    }


    public static int[] movesToStamp(String stamp, String target) {
        // 1.1  字符串转变为字符串
        char[] s = stamp.toCharArray();
        char[] t = target.toCharArray();
        int n = s.length;
        int m = t.length;
        // 初始化图 和 入度表 和 拓扑队列
        if (n > m) {
            return new int[0];
        }
        int len = m - n;

        int[] indegree = new int[len + 1]; // 入度表示 每个位置开头盖下去的错误的次数
        List<List<Integer>> grap = new ArrayList<>();
        Arrays.fill(indegree, n);  // 入度全初始化为 n , 即默认全部的都错误了n

        int l = 0, r = 0;
        int[] queue = new int[len + 1];

        for (int i = 0; i < m; i++) {
            grap.add(new ArrayList<>());
        }
        // 2 统计入度表, 每个位置都盖一遍，统计一遍入度
        for (int i = 0; i <= len; i++) {
            for (int j = 0; j < n; j++) {
                if (s[j] == t[i + j]) {
                    if (--indegree[i] == 0) {
                        queue[r++] = i;
                    }
                } else {
                    // 错误的位置需要记录
                    // from : 错误的位置
                    // to : i开头的下标
                    grap.get(i + j).add(i);
                }
            }
        }
        // 结果统计
        boolean[] visited = new boolean[m];
        int[] res = new int[len + 1];
        int size = 0; // 方便后面的结果统计
        while (l < r) {
            int cur = queue[l++];
            res[size++] = cur;
            for (int i = 0; i < n; i++) {
                // cur ： 开头位置
                // cur + 0, cure + 1 .... cur + n - 1
                if (!visited[cur + i]) {
                    visited[cur + i] = true;
                    for (int next : grap.get(cur + i)) {
                        if (--indegree[next] == 0) {
                            queue[r++] = next;
                        }
                    }
                }
            }
        }
        if (size != len + 1) {
            return new int[0];
        }
        // path逆序调整
        for (int i = 0, j = size - 1; i < j; i++, j--) {
            int tmp = res[i];
            res[i] = res[j];
            res[j] = tmp;
        }

        return res;
    }
}
